package sort;
/**
 * 求小和
 */
public class SmallSort {
    public static void main(String[] args) {
        int[] arr = {3,4,2,1,5};
        int smallSort = process(arr,0,4);
        System.out.println(smallSort);
    }
    public static int process(int[] arr,int L,int R){
        if (L == R){
            return 0;
        }
        int Middle = L + ((R - L)>>1);
        // 求出左侧部分在变有序的过程中产生的小和
        int sumLeft = process(arr,L,Middle);
        // 求出右侧部分在变有序的过程中产生的小和
        int sumRight = process(arr,Middle+1,R);
        // 求出左侧和右侧部分在合并的过程中产生的小和
        int sumMargin = merge(arr,L,Middle,R);
        // 返回
        return sumLeft + sumRight + sumMargin;
    }
    public static int merge(int[] arr,int L,int Middle,int R){
        int[] temp = new int[R - L + 1];
        int index = 0;
        int left = L;
        int right = Middle+1;
        int result = 0;
        while (left <= Middle && right <= R){
            // 在出现左侧小于右侧的时候，就会产生小和，个数是右侧当前数字以及后面的数字(右侧已经排好序)
            result += arr[left] < arr[right] ? arr[left]*(R-right+1) : 0;
            temp[index++] = (arr[left] < arr[right]) ? arr[left++] : arr[right++];
        }
        while (right <= R){
            temp[index++] = arr[right++];
        }
        while (left <= Middle){
            temp[index++] = arr[left++];
        }
        for (int i = L;i <= R; i++) {
            arr[i] = temp[i-L];
        }
        return result;
    }
}
